package com.leetcode.p200;

import com.bean.TreeNode;
import com.utils.TreeUtils;

public class Test236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root.val == p.val || root.val == q.val) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeUtils.buildTree("3,5,1,6,2,0,8,null,null,7,4");
//        TreeNode treeNode = TreeUtils.buildTree4();
        TreeUtils.showTree(treeNode);

        Test236 test = new Test236();
        TreeNode result = test.lowestCommonAncestor(treeNode, new TreeNode(0), new TreeNode(4));
        if (result != null) {
            System.out.println(result.val);
        }
    }

}
